package com.mzy.linear_struct.ks;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Author: mizy3
 * @Date: 2024/08/25/下午4:37
 * @Description:
 */
public class 找到字符串中所有字母异位词 {
    public static List<Integer> findAnagrams(String s, String p) {
        List<Integer> ans = new ArrayList<>();

        if (s.length() < p.length()) {
            // 如果s没p长，直接返回空列表
            return ans;
        }

        int[] c1 = new int[26];
        int[] c2 = new int[26];

        for (int i = 0; i < p.length(); i++) {
            c2[p.charAt(i) - 'a']++;
        }
        int l = 0, r = 0;
        while (r < s.length()) {
            c1[s.charAt(r) - 'a']++;
            if (r - l + 1 > p.length()) {
                c1[s.charAt(l++) - 'a']--;
            }
            if (Arrays.equals(c1, c2)) {
                ans.add(l);
            }
            r++;
        }

        return ans;
    }

    public static void main(String[] args) {
        System.out.println(findAnagrams("cbaebabacd", "abc"));
    }
}


















